package org.aplombh.java.leetcode.all;

public class _28找出字符串中第一个匹配项的下标 {
    public static void main(String[] args) {
//        System.out.println(new Solution28_3().strStr("leetcode", "leeto"));
        System.out.println(new Solution28_3().strStr("leetcode", "leeto"));
    }
}

// 字符串哈希
class Solution28_1 {

    public static final int P = 131;

    long[] hash, hash_sub;
    long[] p;


    long get(int l, int r) {

        // 字符串 abcdefg..  ->  1234567...
        // h[r] = h[0-6] = 0-r                      1234567                 当作p(十进制）进制数，整个数的值
        // h[l] = h[0-4] = 0-l                      12345                 当作p(十进制）进制数，整个数的值
        // h[l-1] = h[0-3] = 0-(l-1)                1234                 当作p(十进制）进制数，整个数的值
        // h[l-1] * p[r-l+1] = h[0-3] * p^3 =       1234000
        // 所以 h[l-r] = h[r] - h[l-1] * p[r-l+1] =  1234567 - 1234000 = 567
        if (l == 0) return hash[r];
        return hash[r] - hash[l - 1] * p[r - l + 1];
    }

    public int strStr(String haystack, String needle) {

        if (haystack.length() == 0) return 0;
        if (haystack.length() < needle.length()) return -1;

        char[] matching = haystack.toCharArray();
        char[] pattern = needle.toCharArray();

        int n = haystack.length();
        int m = needle.length();

        hash = new long[n + 1];
        hash_sub = new long[n + 1];

        p = new long[n + 1];
        p[0] = 1;


        for (int i = 1; i < n; i++) {

            // 指数递增的数组
            // 每位的进制
            p[i] = p[i - 1] * P;
        }

        for (int i = 0; i < n; i++) {
            // 每次乘p 并且加上当前字符的的值
            // hash[i] 存放0-i 当作p进制数的值
            if (i == 0) hash[i] = matching[i];
            else hash[i] = hash[i - 1] * P + matching[i];
        }

        for (int i = 0; i < m; i++) {

            // 每次乘p 并且加上当前字符的ASCII码的值
            // hash[i] 存放0-i 当作p进制数的值
            if (i == 0) hash_sub[i] = pattern[i];
            else hash_sub[i] = hash_sub[i - 1] * P + pattern[i];
        }

        for (int l = 0; l + m - 1 < n; l++) {
            int r = l + m - 1;
            long vl = get(l, r);
            long rl = hash_sub[m - 1];
            if (vl == rl) {
                return l;
            }
        }

        return -1;
    }
}

// 双指针
class Solution28_2 {
    public int strStr(String haystack, String needle) {
        char[] matching = haystack.toCharArray();
        char[] pattern = needle.toCharArray();

        int n = haystack.length();
        int m = needle.length();

        int i = 0;
        int j = 0;

        while (i < n && j < m) {
            if (matching[i] == pattern[j]) {
                i++;
                j++;
            } else {
                i = i - j + 1;
                j = 0;
            }
        }

        if (j == m) {
            return i - j;
        } else {
            return -1;
        }
    }
}

// kmp
class Solution28_3 {
    public int strStr(String haystack, String needle) {

        int[] next = new int[needle.length() + 1];

        char[] matching = haystack.toCharArray();
        char[] pattern = needle.toCharArray();

        int n = matching.length;
        int m = pattern.length;

        // 求next数组就相当于正在一次字符串匹配, next[i] 的值为 i 为结尾的子字符串和 0-j 的子字符串匹配的最长长度
        // next数组、每次在某位置匹配失败, 模式串从第几位开始匹配, 匹配串还是从当前位置开始
        for (int i = 1, j = 0; i < m; i++) {

            // 如果匹配失败, 回退, next为模式串回退到哪步数, 如果回退到第next[j-1]步后仍不匹配, 对比pattern[i]和pattern[j], 如果仍不匹配, 往前递归
            while (j != 0 && pattern[i] != pattern[j]) j = next[j - 1];

            // 如果匹配成功，记录位置
            if (pattern[i] == pattern[j]) j++;

            next[i] = j;
        }

        // 模式匹配
        for (int i = 0, j = 0; i < n; i++) {

            // 如果匹配失败，回退
            while (j != 0 && matching[i] != pattern[j]) j = next[j - 1];

            // 当前位置匹配成功，继续往下匹配

            if (matching[i] == pattern[j]) j++;

            // 模式串匹配成功，输出位置并继续往后匹配
            if (j == m) {
                return i - j + 1;
                // 匹配成功，进行下一次匹配
//                j = next[j - 1];
            }
        }
        return -1;
    }
}